package Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 *  题目 ：包含min函数的栈
 *  题目详述 ：
 *  定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 */
public class MinStack {
    /**
     *  核心思想 ：
     *  （使用辅助栈，辅助栈中存储每一个栈顶元素对应的当前栈中的最小值）
     */
    Deque<Integer> mainStack;
    Deque<Integer> helpStack;
    public MinStack() {
        mainStack = new LinkedList<>();
        helpStack = new LinkedList<>();
        // 即，辅助栈不能为空，push时，需要与辅助栈进行比较（辅助栈中所存储的是，每一个main栈中栈顶元素所对应的当前main占中的最小值）
        helpStack.push(Integer.MIN_VALUE);
    }

    public void push(int x) {
        mainStack.push(x);
        // 特殊情况 ：由于helpStack中所存储的是 Integer.MIN_VALUE（整数中的最小值），
        // 即，若是mainStack是push第一个元素的话（等价于helpStack中只存在Integer.MIN_VALUE），则需要将其直接插入
        if(helpStack.peek() == Integer.MIN_VALUE){
            helpStack.push(x);
            return;
        }
        /**
         *  注意 ：若是一开始就与helpStack的默认初始元素进行比较时，由于其为 Integer.MIN_VALUE（整数中的最小值），必然为假
         */
        // 为保证helpStack栈中（即，当main栈中没有元素时，为保证此处的比较能够进行，需要向辅助栈中插入默认的最小值）
        if(x <= helpStack.peek()){
            helpStack.push(x);
            return;
        }
        helpStack.push(helpStack.peek());
    }

    public void pop() {
        mainStack.pop();
        helpStack.pop();
    }

    public int top() {
        return mainStack.peek();
    }

    public int min() {
        return helpStack.peek();
    }
}
